package dfs;

/**
 * 给定一个二维网格和一个单词，找出该单词是否存在于网格中。
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用
 * https://leetcode-cn.com/problems/word-search/
 *
 * @author: luo
 * @email: luo@nyist.edu.cn
 * @date: 2021/2/8 17:35
 */
public class Exist {
    public static void main(String[] args) {
//        char[][] board = {
//                {'A', 'B', 'C', 'E'},
//                {'S', 'F', 'C', 'S'},
//                {'A', 'D', 'E', 'E'}
//        };
//        String word = "SEE";
//        char[][] board = {{'a', 'a'}};
//        String word = "aaa";
        char[][] board = {
//                {'a', 'a', 'a', 'a'},
//                {'a', 'a', 'a', 'a'},
//                {'a', 'a', 'a', 'a'},
//                {'a', 'a', 'a', 'a'},
                {'a', 'a', 'a', 'b'}
        };
        String word = "aaaa";
//        String word = "aaaaaaaaaaaaaaaaaaaa";
        System.out.println(exist(board, word));
    }

    private static boolean flag;

    public static boolean exist(char[][] board, String word) {
        flag = false;
        char[] chars = word.toCharArray();
        boolean[][] stack = new boolean[board.length][board[0].length];
        if (chars.length > board.length * board[0].length) {
            return false;
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (chars[0] == board[i][j]) {
                    stack[i][j] = true;
                    backtracking(1, i, j, chars, board, stack);
                    stack[i][j] = false;
                    if (flag) {
                        return true;
                    }
                }


            }
        }

        return false;
    }

    private static void backtracking(int n, int i, int j, char[] chars, char[][] board, boolean[][] stack) {
        if (flag) {
            return;
        }
        if (n == chars.length) {
            flag = true;
            return;
        }
        if (i < board.length - 1 && chars[n] == board[i + 1][j] && !stack[i + 1][j]) {
            stack[i + 1][j] = true;
            backtracking(n + 1, i + 1, j, chars, board, stack);
            stack[i + 1][j] = false;
        }
        if (i > 0 && chars[n] == board[i - 1][j] && !stack[i - 1][j]) {
            stack[i - 1][j] = true;
            backtracking(n + 1, i - 1, j, chars, board, stack);
            stack[i - 1][j] = false;
        }
        if (j < board[0].length - 1 && chars[n] == board[i][j + 1] && !stack[i][j + 1]) {
            stack[i][j + 1] = true;
            backtracking(n + 1, i, j + 1, chars, board, stack);
            stack[i][j + 1] = false;
        }
        if (j > 0 && chars[n] == board[i][j - 1] && !stack[i][j - 1]) {
            stack[i][j - 1] = true;
            backtracking(n + 1, i, j - 1, chars, board, stack);
            stack[i][j - 1] = false;
        }
    }
}
